/**
 * 31. 下一个排列
 * https://leetcode-cn.com/problems/next-permutation/
 */
const { displayBaseArray } = require('../../libs/public');

function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

function resolveHeap(heap, length, offset) {
  if (length < 2) {
    return;
  }
  for (let i = Math.floor(length / 2) - 1; i >= 0; i -= 1) {
    const val = heap[i + offset];
    const left = i * 2 + 1;
    const leftVal = heap[left + offset];
    const right = left + 1;
    const rightVal = right >= length ? Infinity : heap[right + offset];
    if (val <= leftVal && val <= rightVal) {
      continue;
    }
    if (leftVal <= rightVal) {
      swap(heap, i + offset, left + offset);
    } else {
      swap(heap, i + offset, right + offset);
    }
  }
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums) {
  let index = nums.length - 1;
  for (; index > 0; index -= 1) {
    if (nums[index - 1] < nums[index]) {
      break;
    }
  }
  if (index < 1) {
    nums.reverse();
    return;
  }
  for (let i = index; i < nums.length; i += 1) {
    resolveHeap(nums, nums.length - i, i);
  }
  const left = index - 1;
  const leftVal = nums[left];
  for (let i = index; i < nums.length; i += 1) {
    if (nums[i] > leftVal) {
      swap(nums, left, i);
      break;
    }
  }
}

let nums = [1, 2, 3];
nextPermutation(nums);
console.log(displayBaseArray(nums) === '[1,3,2]');
nums = [3, 2, 1];
nextPermutation(nums);
console.log(displayBaseArray(nums) === '[1,2,3]');
nums = [1, 1, 5];
nextPermutation(nums);
console.log(displayBaseArray(nums) === '[1,5,1]');
